In multi-key memory encryption, a system memory is encrypted with more than one key to secure information and provide isolation to different entities seeking access to the memory. Currently, multi-key technology has a scalability problem, as complexities exist in identifying an appropriate key for use with a given portion of the memory. To this end, a key selector/identifier is used to identify the relevant key. One mechanism to communicate the key identifier is to utilize unused physical address bits (unused because not all system memory is populated). This approach has inherent scalability problems, as it steals memory address space that could otherwise be used for addressing memory. Adding additional address bits or other metadata consumes additional die area, and thus increases cost and decreases performance. As more traditional enterprise workloads move to cloud computing environments, data protection/encryption is becoming a foundational requirement, from cloud service providers (CSPs) to hardware and system vendors. However, supporting a key per tenant of a CSP to help achieve cryptographic isolation between different CSP customers comes at a high cost of complexity and limits scalability.